"""
得到一个数组的全排列
leetcode上看到一个算法

定义一个数组 ans = [[]]
然后迭代l，
在迭代每一个元素的时候，ans保留原来的数组再加上所有的元素加上那个元素：

例子：
l=[1, 2 , 3, 4]
ans = [[]]

>1
 [[], [1]]

>2
 [[], [1], [1, 2], [2]]

>3

 [[], [1], [1, 2], [2], [3], [1, 3], [1, 2, 3], [2, 3]]

这谁能想到。。。
"""

"""
使用回溯算法

每次回溯不包含自己的元素
"""

from typing import List

def permute(l: List, n: int):
    ans = []
    def helper(array: List, res: List,  count: int):
        if count == 0:
            ans.append(res)
            return 
        for i in range(len(array)):
            helper(array[:i]+ array[i+1:], res + [array[i]], count - 1)
    helper(l, [], n)
    return ans

if __name__ == "__main__":
    print(permute([1,2,3,4], 3))